1. Field of the Invention
Embodiments of the present general inventive concept relate to a modular calculator, and more particularly, when a modular addition or a modular subtraction is performed, to a method of performing an arithmetic operation, by using each sign information of two integers necessary for the modular addition or subtraction, on one of addition and subtraction of the two integers and a modulus value, and devices to perform the method.
2. Description of the Related Art
A modulus reduction method performed in a modulus operation multiplies two integers and calculates the remainder after dividing a multiplication result by a modulus. However, division requires much calculation, so that a general modular reduction method is not used in a cryptographic operation using great integer values.
In a cryptographic operation instead of a general modular reduction method, a Montgomery multiplication method is widely used.
In case of a general modular reduction method, a trial division, a process of dividing for calculating a quotient in division, is required. However, it is possible to calculate a quotient of a reduction operation only using an acknowledged value in case of Montgomery multiplication using a Montgomery algorithm, so that it is easy to be embodied.
In particular, a Montgomery multiplication is possible to be embodied at a low cost since it may replace a general division with a division of involution of 2 which is easily embodied in a right-shifter.
Similarly, a general method may be considered in a modular reduction method in a modular addition or a modular subtraction. That is, the remainder is calculated by adding two integers and dividing a result by a modulus. However, in this case, a median calculated by adding two integers does not deviate from a modulus value greatly, unlike a modulus multiplication in which the multiplication of the two integers may greatly deviate from the modulus value. As such, a modular reduction is possible not through division but through subtraction. That is, after calculating a median, a modulus is subtracted only in case the median is more than a modulus value, and the median is output as it is in the other cases. A modulus subtraction is performed in the same way. When there is a negative number after comparing a median calculated by subtracting two integers with 0, a modulus is added. Otherwise, a median is output as it is.